
import java.util.Arrays;
import java.util.Random;

public class T {

    public static void main1(String[] args) {
        int[] a={273,34,67,22,11,66,8,3};
        for (int i = (a.length-1-1)/2; i >=0 ; i--) {
            shiftDown(a,i,a.length-1);
        }




       int[]arr= Arrays.copyOf(a,2*a.length);
        System.out.println(Arrays.toString(a));
        arr[8]=5;

        shiftUp(arr,8);
        System.out.println(Arrays.toString(arr));





    }

    public static void shiftDown(int[] array, int parent,int len) {

        int child=2*parent+1;  //父节点的左孩子
        while(child<=len){

            if(child+1<=len&&array[child+1]<array[child]){
                child=child+1;

            }

            if(array[child]<array[parent]){
                swap(array,child,parent);
            }

            parent=child;
            child=2*child+1;



        }



    }

    private static void swap(int[] array, int child, int parent) {
        int tmp=array[child];
        array[child]=array[parent];
        array[parent]=tmp;

    }


    public static void shiftUp(int[] array, int child) {

        int parent=(child-1)/2;
        while(child>0){
            if(array[child]<array[parent]){
                swap(array,child,parent);
                child=parent;
                parent=(child-1)/2;

            }else {
                break;
            }


        }
    }

    public static void main(String[] args) {
        int[] arr=new int[10];
        Random random=new Random();

        for (int i = 0; i < 10; i++) {
            int n= random.nextInt(100);
            arr[i]=n;
            shiftUp(arr,i);
        }

        System.out.println(Arrays.toString(arr));
    }


}
